home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 5 / Skunkware 5.iso / src / Tools / libwais / ir / sighash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-05-03  |  10.2 KB  |  328 lines
  1. /* WIDE AREA INFORMATION SERVER SOFTWARE:
  2.    No guarantees or restrictions.  See the readme file for the full standard
  3.    disclaimer.
  4.  
  5.    Brewster@think.com
  6. */
  7.  
  8. /* The memory hashtables for building an index. */
  9. /* -brewster 5/90 */
  10.  
  11. /* main functions:
  12.  *   add_word
  13.  *   finished_add_word
  14.  *   look_up_word
  15.  *
  16.  * The idea is to store up a bunch of words before going to disk.
  17.  * A word entry points to where it will go on disk, and
  18.  * accumulates the entries before doing it.
  19.  *
  20.  * Some of the policy issues in this file are:
  21.  *   How much weight should the first occurance of a word in a document get
  22.  *   over the other occurances.  The first occurance should be worth more
  23.  *   so that words with 3 occurances of "dog" and not "cat"'s should not 
  24.  *   win out over 1 "dog" and 1 "cat" if the question is "Tell me about cats
  25.  *   torture dogs"
  26.  *   The extra weight is 5 at this point.
  27.  *
  28.  */
  29.  
  30. #ifndef lint
  31. static char *RCSid = "$Header: /proj/wais/wais-8-b5/ir/RCS/sighash.c,v 1.23 92/05/05 13:21:25 shen Exp Locker: shen $";
  32. #endif
  33.  
  34. /* Change log:
  35.  * $Log:    sighash.c,v $
  36.  * Revision 1.23  92/05/05  13:21:25  shen
  37.  * undo the change make in previous revision 1.22
  38.  * fixed the bug in db->total_word_ccount by checking the last word in t
  39.  * table. If the last word is DICTIONARY_TOTAL_SIZE_WORD, decrement the number
  40.  * of words to add to dictionary file by 1.
  41.  * 
  42.  * Revision 1.22  92/05/05  11:01:54  shen
  43.  * fixed db->total_word_count for incremental update by eliminating adding
  44.  * DICTIONARY_TOTAL_SIZE_WORD to hash table.
  45.  * 
  46.  * Revision 1.21  92/04/29  08:21:15  shen
  47.  * redefine MAX_OCCURANCES to a very big number: 0x10000000.
  48.  * 
  49.  * Revision 1.20  92/03/20  11:04:18  jonathan
  50.  * Added word_postition argument to add word.  See irext.h for explanation.
  51.  * 
  52.  * Revision 1.19  92/03/01  16:11:57  brewster
  53.  * took out analyze_hashtable_distribution
  54.  * 
  55.  * Revision 1.18  92/02/24  19:58:04  jonathan
  56.  * Added code to add the dictionary to the hastable on startup.
  57.  * 
  58.  * Revision 1.17  92/02/12  13:46:18  jonathan
  59.  * Added "$Log" so RCS will put the log message in the header
  60.  * 
  61. */
  62.  
  63. /* To Do:
  64.  *  done: Improve the hashing functions.
  65.  *  done: stop inserting into hash table after max number have been accumulated
  66.  *  done: make flush not flush buffers that are too big.
  67.  */
  68.  
  69. #include <ctype.h>
  70. #include <string.h>     /* for strlen(), memset() */
  71.  
  72. #include "panic.h"
  73. #include "cutil.h"
  74. #include "futil.h"
  75. #include "irfiles.h"
  76. #include "irhash.h"
  77. #include "stoplist.h"
  78. #include "irinv.h"
  79. #include "sigindex.h"
  80.  
  81. #ifdef UNIX
  82. #define PRINT_AS_INDEXING true /* also defined in irtfiles.c and irfiles.c */
  83. #else 
  84. #define PRINT_AS_INDEXING false
  85. #endif
  86.  
  87. #define PROXIMITY /* this turns on writing out of all word occurances */
  88.  
  89.  
  90. /* ---------------------------------------------------- */
  91. static hash_entry* look_up_word _AP((char* word,hashtable*
  92.                      the_word_memory_hashtable));
  93.   
  94. static hash_entry* 
  95. look_up_word(word,the_word_memory_hashtable)
  96. char* word;
  97. hashtable* the_word_memory_hashtable;
  98. {
  99.   hash_entry * answer = get_hash(word, the_word_memory_hashtable);
  100.   
  101.   if(NULL != answer)
  102.     return(answer);
  103.   else{
  104.     hash_entry wrd_entry;
  105.     answer = put_hash(word, the_word_memory_hashtable, &wrd_entry);
  106.     answer->number_of_occurances = 0;
  107.     answer->memory_ptr = NULL;
  108.     answer->memory_size = 0;
  109.     answer->current_memory_ptr = answer->memory_ptr;
  110.     answer->current_doc_id = 0;
  111.     return(answer);
  112.   }
  113. }
  114.  
  115. #ifdef NOTUSED
  116. static unsigned char add_weight _AP((long current_weight,long new_weight));
  117.  
  118. static unsigned char 
  119. add_weight(current_weight,new_weight)
  120. long current_weight;
  121. long new_weight;
  122. /* add a new weight to the existing one */
  123. {
  124.   /* this should be smarter than this, like doing the log or something */
  125.   if(127 < (current_weight + new_weight)){
  126.     /* the max char.  should be 255, but does not work on all compilers */
  127.     return(127);
  128.   }
  129.   else{
  130.     return(current_weight + new_weight);
  131.   }
  132. }
  133.  
  134. long write_bytes_to_memory(value,size,ptr)
  135. long value;
  136. long size;
  137. unsigned char* ptr;
  138. {
  139.   /* writes the number into memory lsb first.  
  140.      returns the number of bytes written */
  141.   long i;
  142.   long original_value = value;
  143.  
  144.   if(size < 0) /* paranoia */
  145.     panic("attempting to write a negative number of bytes");
  146.  
  147.   ptr += size; /* start at the end of the block and write backwards */
  148.   for (i = 0; i < size; i++){
  149.     ptr--;
  150.     *ptr = (unsigned char)(value & 0xFF);
  151.     value = value >> 8;
  152.   }
  153.   if(value != 0)
  154.     panic("In a call to write_bytes_to_memory, the value %ld can not be represented in %ld bytes", original_value, size);
  155.  
  156.   return(size);
  157. }
  158.         
  159. #endif /* def NOTUSED */
  160.  
  161. /* adds a word to the hashtable. 
  162.  * Returns the 0 if successful. See irext.h for more documentation.
  163.  */
  164. long add_word(word, char_pos, line_pos,
  165.           weight, doc_id, date, word_pair, db, word_position)
  166.      char *word;    /* the word to be indexed, this could be a
  167.                word pair. If NULL there are no more words
  168.                to be indexed */
  169.      long char_pos;    /* the position of the start of the
  170.                word */
  171.      long line_pos;    /* this is passed for the best
  172.                section calculation */
  173.      long weight;    /* how important the word looks
  174.                syntactically (such as is it bold)
  175.                NOT used by signature system */
  176.      long doc_id;     /* current document, this will never be 0 */
  177.      time_t date; /* display day of this document, 0 if not known */
  178.      long word_pair;
  179.      database* db; /* database to insert the document */
  180.      boolean word_position; /* ignored here. */
  181. {
  182.   /* look up the word in the hashtable */
  183.   /* creates it if necessary */    
  184.   hash_entry* wrd_entry;
  185.   hashtable * the_word_memory_hashtable = db->the_word_memory_hashtable;
  186.   /* printf("Word: '%s' doc_id: %ld, pos: %ld, weight: %ld\n",
  187.      word, doc_id, char_pos, weight); */
  188.   
  189.   if(NULL == db->the_word_memory_hashtable){
  190.     panic("The memory word hashtable is not defined.");
  191.   }
  192.  
  193.   /* if we have indexed enough words flush the memory copies to disk.
  194.   if(db->number_of_words_in_hashtable == db->flush_after_n_words)
  195.     flush_memory_hashtable_to_disk(db, false);
  196.     ** not done on sig system **
  197.  */
  198.   
  199.   wrd_entry = look_up_word(word, the_word_memory_hashtable);
  200.   wrd_entry->number_of_occurances ++;
  201.  
  202.   /* check if we have too many of this word before we add it */
  203. #undef MAX_OCCURANCES
  204. #define MAX_OCCURANCES 0x10000000
  205.   if(wrd_entry->number_of_occurances < MAX_OCCURANCES){
  206.     db->number_of_words_in_hashtable ++;
  207.     sig_add_word(word, char_pos, line_pos, weight, doc_id, date, word_pair);
  208.   }
  209.   return(0L);
  210. }
  211.  
  212. void add_stop_words(the_word_memory_hashtable)
  213. hashtable *the_word_memory_hashtable;
  214.      /* add the stop words to the hashtable.  this must be done before
  215.     adding other words */
  216. {
  217.   init_stop_list();
  218.   while(true){
  219.     char *word = next_stop_word();
  220.     hash_entry* wrd_entry;
  221.  
  222.     if(NULL == word)
  223.       break;
  224.     wrd_entry = look_up_word(word, the_word_memory_hashtable);
  225.     wrd_entry->number_of_occurances = STOP_WORD_FLAG;
  226.   }
  227. }
  228.  
  229.  
  230. long finished_add_word(db)
  231. database *db;
  232. {
  233.   /* write out the dictioanry */
  234.   long i;
  235.   long num_words;
  236.  
  237.   db->number_of_words = hashtable_count(db->the_word_memory_hashtable);
  238.   init_dict_file_for_writing(db);
  239.   /* analyze_hashtable_distribution(db->the_word_memory_hashtable); */
  240.   sort_hashtable(db->the_word_memory_hashtable);
  241.   /* exclude the last word which is DICTIONARY_TOTAL_SIZE_WORD */
  242.   num_words = hashtable_count(db->the_word_memory_hashtable);
  243.   if ( 0 == strcmp(db->the_word_memory_hashtable->contents[num_words-1].key,
  244.                    DICTIONARY_TOTAL_SIZE_WORD) ) 
  245.     num_words--;
  246.    
  247.   for(i = 0; i < num_words; i++){
  248.     hash_entry * entry = &db->the_word_memory_hashtable->contents[i];
  249.     if(0 == (STOP_WORD_FLAG & entry->number_of_occurances)){
  250.       /* write out the dictionary entry */
  251.       /* printf("Adding word: %s %ld entries\n", entry->word, entry->number_of_occurances); */
  252.       /* the position in this world is a unique id for every word */
  253.       add_word_to_dictionary(entry->key, i,
  254.                  entry->number_of_occurances, db);
  255.     }
  256.   }
  257.   finished_add_word_to_dictionary(db);
  258.   return(sig_finished_add_word(db));
  259. }
  260.  
  261. /* Add the dictionary to the hastable */
  262.  
  263. void add_dictionary_to_hashtable(db)
  264. database *db;
  265. {
  266.   /* prints the contents of a dictionary */
  267.   FILE *stream = db->dictionary_stream;
  268.   long i, j, new_number_of_dictionary_blocks;
  269.   extern unsigned char *dictionary_header_block, *dictionary_block;
  270.   extern long number_of_dictionary_blocks;
  271.  
  272.   if(stream != NULL) {
  273.     waislog(WLOG_LOW, WLOG_INFO, "Adding dictionary to hastable");
  274.  
  275.     s_fseek(stream, 0L, SEEK_SET);
  276.     new_number_of_dictionary_blocks = read_bytes(DICTIONARY_HEADER_SIZE, stream);
  277.     if(new_number_of_dictionary_blocks > number_of_dictionary_blocks)
  278.       dictionary_header_block = NULL;
  279.     number_of_dictionary_blocks = new_number_of_dictionary_blocks;
  280.     if(NULL == (dictionary_header_block =
  281.         read_dictionary_block(dictionary_header_block,
  282.                       DICTIONARY_HEADER_SIZE,
  283.                       number_of_dictionary_blocks,
  284.                       stream))) {    
  285.       waislog(WLOG_MEDIUM, WLOG_WARNING,
  286.           "Could not read dictionary header block");
  287.       return;
  288.     }
  289.     for(i = 0; i < number_of_dictionary_blocks; i++){
  290.       long pos = dictionary_block_position(i, dictionary_header_block);
  291.       if(NULL == (dictionary_block =
  292.           read_dictionary_block(dictionary_block,
  293.                     pos, DICTIONARY_BLOCK_SIZE, stream))) {
  294.     waislog(WLOG_MEDIUM, WLOG_WARNING,
  295.         "Could not read dictionary block %ld", pos);
  296.       }
  297.       else
  298.     /* iterate over words */
  299.     for(j = 0; j < DICTIONARY_BLOCK_SIZE; j++) {
  300.       char *word = dictionary_block_word(j, dictionary_block);
  301.       hash_entry* wrd_entry;
  302.  
  303.       if(word[0] == '\0' )
  304.         break;
  305.       wrd_entry = look_up_word(word, db->the_word_memory_hashtable);
  306.       wrd_entry->number_of_occurances = 
  307.         dictionary_block_word_occurances(j, dictionary_block);
  308.     }
  309.     }
  310.   }
  311. }
  312.  
  313. long init_add_word(db, hashtable_size, flush_after_n_words)
  314.      database *db;
  315.      long hashtable_size;
  316.      long flush_after_n_words;
  317. {
  318.   if(NULL != db->the_word_memory_hashtable)
  319.     free_hashtable(db->the_word_memory_hashtable);
  320.   db->the_word_memory_hashtable =
  321.     make_hashtable(0, hashtable_size, sizeof(hash_entry));
  322.   db->flush_after_n_words = 0x7FFFFFFF;  /* a large number */
  323.   sig_init_add_word(db, BATCH_UPDATE, ADD_UPDATE);
  324.   add_dictionary_to_hashtable(db);
  325.   add_stop_words(db->the_word_memory_hashtable);
  326.   return(0);
  327. }
  328.